#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100

typedef struct{
    int key;
}ElementType;

typedef struct{
    ElementType r[MAX_SIZE];
    int length;
} Sqlist;

//直接插入排序
void InsertSort(Sqlist*L)
{
    int i,j;
    for(i=2;i<=L->length;i++)
    {//从第二个元素开始插入
        if(L->r[i].key<L->r[i-1].key)
        {
            L->r[0]=L->r[i];
            for(j=i-1;j>=0&&L->r[0].key<L->r[j].key;j--)
            {
                L->r[j+1]=L->r[j];
            }
            L->r[j+1]=L->r[0];
        }
    }
}


//冒泡排序函数
void BubbleSort(Sqlist*L)
{
    int i,j;
    int temp;
    for(i=0;i<L->length-1;i++)
    {
        for(j=0;j<L->length-1;j++)
        {
            if(L->r[j].key>L->r[j+1].key)
            {
                temp=L->r[j].key;
                L->r[j].key=L->r[j+1].key;
                L->r[j+1].key=temp;
            }
        }
    }
}

//分割函数
int partition(Sqlist*L,int low,int high)
{
    int pivotkey;
    pivotkey=L->r[low].key;
    while(low<high)
    {
        while(low<high&&L->r[high].key>=pivotkey)
        {
            high--;
        }
        L->r[low]=L->r[high];
        while(low<high&&L->r[low].key<=pivotkey)
        {
            low++;
        }
        L->r[high]=L->r[low];
    }
    L->r[high].key<L->r[low].key;
    return low;
}

//快速排序
void quickSort(Sqlist*L,int low,int high)
{
    if(low<high)
    {
        int pivotIndex=partition(L,low,high);
        quickSort(L,low,pivotIndex-1);
        quickSort(L,pivotIndex+1,high);

    }
}



//查找最小元素索引
int SelectMinKey(Sqlist*L,int low,int high)
{
    int minIndex=low;
    for(int i=low+1;i<high;i++)
    {
        if(L->r[i].key<L->r[minIndex].key)
        {
            minIndex=i;
        }
    }
    return minIndex;
}

//交换俩个元素
void swap(Sqlist*L,int i,int j)
{
    ElementType temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}

//简单选择排序
void SelectSort(Sqlist*L)
{
    int i,j;
    for(i=0;i<L->length-1;i++)
    {
        j=SelectMinKey(L,i,L->length);
        if(i!=j)
        {
            swap(L,i,j);
        }
    }
}

void PrintList(Sqlist*L)
{
    for(int i=0;i<L->length;i++)
    {
        printf("%d ",L->r[i].key);
    }
    printf("\n");
}

int main()
{
    Sqlist L={{5,2,9,1,5,6},6,};
    printf("Before sorting:");
    PrintList(&L);
    //InsertSort(&L);//直接插入排序
    // BubbleSort(&L);//冒泡排序
    //quickSort(&L,0,L.length-1);//快速排序
    SelectSort(&L);
    printf("After sorting:");
    PrintList(&L);
    return 0;
}